%0 Conference Proceedings
%4 sid.inpe.br/sibgrapi@80/2007/07.09.17.59
%2 sid.inpe.br/sibgrapi@80/2007/07.09.17.59.10
%@doi 10.1109/SIBGRAPI.2007.15
%T An Exact and Efficient Algorithm for the Orthogonal Art Gallery Problem
%D 2007
%A Couto, Marcelo C.,
%A Souza, Cid C. de,
%A Rezende, Pedro J. de,
%@affiliation Institute of Computing, State University of Campinas, Campinas - Brazil
%@affiliation Institute of Computing, State University of Campinas, Campinas - Brazil
%@affiliation Institute of Computing, State University of Campinas, Campinas - Brazil
%E Falcão, Alexandre Xavier,
%E Lopes, Hélio Côrtes Vieira,
%B Brazilian Symposium on Computer Graphics and Image Processing, 20 (SIBGRAPI)
%C Belo Horizonte, MG, Brazil
%8 7-10 Oct. 2007
%I IEEE Computer Society
%J Los Alamitos
%S Proceedings
%K Art Gallery, Exact Solution, Orthogonal Polygons, Integer Programming, Set Covering.
%X In this paper, we propose an exact algorithm to solve the Orthogonal Art Gallery problem in which guards can only be placed on the vertices of the polygon $ P$ representing the gallery. Our approach is based on a discretization of $ P$ into a finite set of points in its interior. The algorithm repeatedly solves an instance of the Set Cover problem obtaining a minimum set $ Z$ of vertices of $ P$ that can view all points in the current discretization. Whenever $ P$ is completely visible from $ Z$ , the algorithm halts; otherwise, the discretization is refined and another iteration takes place. We establish that the algorithm always converges to an optimal solution by presenting a worst case analysis of the number of iterations that could be effected. Even though these could theoretically reach $ O(n^4)$ , our computational experiments reveal that, in practice, they are linear in $ n$ and, for $ n\leq 200$ , they actually remain less than three in almost all instances. Furthermore, the low number of points in the initial discretization, $ O(n^2)$ , compared to the possible $ O(n^4)$ atomic visibility polygons, renders much shorter total execution times. Optimal solutions found for different classes of instances of polygons with up to 200 vertices are also described.
%@language en
%3 couto-ArtGallery.pdf